package com.mdnote.practice.dp;

import java.util.Arrays;

/**
 * @author Rhythm-2019
 * @version 1.0
 * @date 2020/9/20
 * @description 零钱兑换
 */
public class LeetCode322 {

    private static final int INF = Integer.MAX_VALUE - 10;

    public static void main(String[] args) {
        LeetCode322 leetCode322 = new LeetCode322();
//        int res = leetCode322.coinChange(new int[]{186,419,83,408}, 6249);
        int res = leetCode322.coinChange(new int[]{9, 10}, 18);
        System.out.println(res);
    }
    public int coinChange(int[] coins, int amount) {
        if (coins.length == 0) {
            return - 1;
        }
        if (amount == 0) {
            return 0;
        }
        // recursion
        return recursion(0, coins, amount);
        // DP
//        return re(coins, amount);
    }

    /**
     * 分析： 1. 重复子问题：当前金币Spend(current_coin) = Min(Spend(current_coin - i) + 1
     *          我们应该从0 -> account 进行DP
     *       2. DP数组：do[i] i 金币  dp[i]  凑到i需要的硬币数
     *       3. DP方程 for coin in coins: dp[i] = Math.min(dp[i - coin]) + 1
     * @param coins
     * @param amount
     * @return
     */
    private int dp(int[] coins, int amount) {

        // 初始化数组
        int[] dp = new int[amount + 1];
        Arrays.fill(dp, INF);

//        int[] dp = new int[amount + 1];
//        for (int i = 0; i < coins.length; i++) {
//            if (coins[i] < dp.length) {
//                dp[coins[i]] = 1;
//            }
//        }
        // 很关键，只需要初始化这个0就可以了
        dp[0] = 0;
        // DP
        for (int i = 1; i < dp.length; i++) {
            int min =INF;
            for (int coin : coins) {
                if (i - coin >= 0) {
                    min = Math.min(min, dp[i - coin]);
                }
            }
            if (min != INF) {
                dp[i] = min + 1;
            }


        }
        System.out.println(dp[amount]);
        return dp[amount] == INF? -1 :dp[amount];
    }

    private int dp2(int[] coins, int amount) {

        // 初始化数组
        int[] dp = new int[amount + 1];

        // 这里填充一个比较大的数，为了后面的比较大小
        Arrays.fill(dp, amount + 1);
        // i - coin == 0时需要用到
        dp[0] = 0;
        // DP
        for (int i = 1; i < dp.length; i++) {
            for (int coin : coins) {
                if (i - coin >= 0) {
                    dp[i] = Math.min(dp[i], dp[i - coin] + 1);
                }
            }
        }
        return dp[amount] == amount + 1 ? -1 :dp[amount];
    }
    private int recursion(int current_coin, int[] coins, int amount) {
        // Terminator
        if (current_coin == amount) {
            return 0;
        }
        if (current_coin > amount) {
            return INF;
        }
        // Process current logic
        int res = INF;
        for (int coin : coins) {
            int temp = recursion(current_coin + coin, coins, amount);
            if (temp == INF) {
                continue;
            }
            res = Math.min(res, temp + 1);
        }
        // Drill down

        // Restore current data
        return res;
    }
}
